import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-08-03
 * Time: 20:31
 */

class MyStack {
    public Deque<Integer> que1;
    public Deque<Integer> que2;
    public MyStack() {
        this.que1 = new LinkedList<>();
        this.que2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!que1.isEmpty()) {
            que1.offer(x);
        }else if(!que2.isEmpty()) {
            que2.offer(x);
        }else {
            que1.offer(x);
        }
    }

    public int pop() {
        if(!que1.isEmpty()) {
            int size = que1.size();
            for(int i = 0; i < size-1; i++) {
                que2.offer(que1.poll());
            }
            return que1.poll();
        }else if(!que2.isEmpty()) {
            int size = que2.size();
            for(int i = 0; i < size-1; i++) {
                que1.offer(que2.poll());
            }
            return que2.poll();
        }
        return Integer.MIN_VALUE;
    }

    public int top() {
        if(!que1.isEmpty()) {
            int tmp = 0;
            while(!que1.isEmpty()) {
                tmp = que1.poll();
                que2.offer(tmp);
            }

            return tmp;
        }else if(!que2.isEmpty()) {
            int tmp = 0;
            while(!que2.isEmpty()) {
                tmp = que2.poll();
                que1.offer(tmp);
            }

            return tmp;
        }
        return Integer.MIN_VALUE;
    }

    public boolean empty() {
        return que1.isEmpty() && que2.isEmpty();
    }
}

class MyQueue {
    public Stack<Integer> stack1;
    public Stack<Integer> stack2;
    public MyQueue() {
        this.stack1 = new Stack<>();
        this.stack2 = new Stack<>();
    }

    public void push(int x) {
        if(!stack2.empty()) {
            while(!stack2.empty()) {
                stack1.push(stack2.pop());
            }
        }
        stack1.push(x);
    }

    public int pop() {
        while(!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();

    }

    public int peek() {
        while(!stack1.empty()) {
            stack2.push(stack1.pop());
        }

        return stack2.peek();
    }

    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}
public class Test {
}
